{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3c31470c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from graphviz import Digraph\n",
    "data = pd.read_csv(\"water.csv\")\n",
    "\n",
    "ori_data = data.to_numpy()\n",
    "\n",
    "std_data = np.delete(ori_data, 0, axis=1)\n",
    "\n",
    "idx_name = data.columns[1:-1].to_numpy()\n",
    "\n",
    "\n",
    "def entropy(D):\n",
    "    _, cnt = np.unique(D[:, -1], return_counts=True)\n",
    "    p = cnt / len(D[:, -1])\n",
    "    ent = -np.sum(p * np.log2(p))\n",
    "    return ent\n",
    "\n",
    "\n",
    "def infoGain(D, attr):\n",
    "    sigma = 0;\n",
    "    attr_value=np.unique(D[:, attr])\n",
    "    D_size = len(D)\n",
    "    D_ent = entropy(D)\n",
    "    for val in attr_value:\n",
    "        subset_size = len(D[D[:, attr] == val])\n",
    "        subset_ent = entropy(D[D[:, attr] == val])\n",
    "        sigma += (subset_size / D_size) * subset_ent\n",
    "    gain = D_ent - sigma\n",
    "    return gain\n",
    "        \n",
    "\n",
    "def majorityLabel(labels):\n",
    "    # 从给定的标签集合中返回占多数的标签\n",
    "    unique_labels, counts = np.unique(labels, return_counts=True)\n",
    "    max_count_idx = np.argmax(counts)\n",
    "    return unique_labels[max_count_idx]\n",
    "\n",
    "def TreeGenerate(D, A):\n",
    "        # 只有一个标签说明到叶子节点\n",
    "        if (len(np.unique(D[:, -1])) == 1):\n",
    "            return D[0, -1]\n",
    "        # A为空集,返回数量最多的标签\n",
    "        if(len(A) == 0):\n",
    "            _, lable = np.unique(D[:, -1],return_inverse=True)\n",
    "            idx_max = np.argmax(np.bincount(lable)) # 返回最大值的索引\n",
    "            return _[idx_max]\n",
    "        \n",
    "        # 选择最优划分属性\n",
    "        \n",
    "        best_gain = 0\n",
    "        best_attr = None\n",
    "        best_val = None\n",
    "        \n",
    "        for attr in range(len(A)):\n",
    "            # 计算信息增益\n",
    "            gain = infoGain(D, attr)\n",
    "            if(gain > best_gain):\n",
    "                best_gain = gain\n",
    "                best_attr = attr\n",
    "                \n",
    "        if(best_attr == None):\n",
    "            return None;\n",
    "        # 递归创建子节点\n",
    "        attr_name = A[best_attr]\n",
    "        \n",
    "        subtree = {attr_name: {}}\n",
    "        attr_value=np.unique(D[:, best_attr])\n",
    "        for v in attr_value:\n",
    "            D_attr_val = D[D[:, best_attr] == v]\n",
    "            subtree[attr_name][v] = TreeGenerate(D_attr_val, np.delete(A, best_attr))\n",
    "        return subtree\n",
    "    \n",
    "    \n",
    "    \n",
    "Tree = TreeGenerate(std_data, idx_name)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5718f1c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'纹理': {'模糊': '否', '清晰': {'根蒂': {'硬挺': '否', '稍蜷': {'色泽': {'乌黑': None, '青绿': '是'}}, '蜷缩': '是'}}, '稍糊': {'色泽': {'乌黑': {'脐部': {'沉闷': '否', '浊响': '是'}}, '浅白': '否', '青绿': '否'}}}}\n"
     ]
    }
   ],
   "source": [
    "child_list = [\"是\",\"否\"]\n",
    "def visualize_data(data, par_node = None, par_edge_lable = None, graph = None):\n",
    "    if(graph is None):\n",
    "        graph = Digraph(comment=\"决策过程\")\n",
    "    if(type(data) != dict):\n",
    "        return\n",
    "    for key, val in data.items():\n",
    "        node_lable = str(key)\n",
    "        if par_node is not None:\n",
    "            graph.edge(str(par_node), node_lable, label=str(par_edge_lable))\n",
    "        graph.node(node_lable)\n",
    "        visualize_data(val, node_lable, key)\n",
    "        return graph\n",
    "        \n",
    "    \n",
    "\n",
    "print(Tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8946d94",
   "metadata": {},
   "outputs": [],
   "source": [
    "dot.clear()\n",
    "dot.node(\"A\", \"纹理\")\n",
    "dot.node(\"B\", \"根蒂\")\n",
    "dot.node(\"C\", \"色泽\")\n",
    "dot.node(\"D\", \"色泽\")\n",
    "dot.node(\"E\", \"脐部\")\n",
    "dot.node(\"F\", \"否\")\n",
    "dot.node(\"G\", \"否\")\n",
    "dot.node(\"H\", \"否\")\n",
    "dot.node(\"I\", \"否\")\n",
    "dot.node(\"J\", \"否\")\n",
    "dot.node(\"K\", \"是\")\n",
    "dot.node(\"L\", \"否\")\n",
    "dot.node(\"M\", \"否\")\n",
    "dot.edge(\"A\", \"F\", label=\"模糊\")\n",
    "dot.edge(\"A\", \"B\", label=\"清晰\")\n",
    "dot.edge(\"B\", \"G\", label=\"硬挺\")\n",
    "dot.edge(\"B\", \"C\", label=\"稍蜷\")\n",
    "dot.edge(\"C\", \"H\", label=\"青绿\")\n",
    "dot.edge(\"B\", \"I\", label=\"蜷缩\")\n",
    "dot.edge(\"A\", \"D\", label=\"稍糊\")\n",
    "dot.edge(\"D\", \"E\", label=\"乌黑\")\n",
    "dot.edge(\"E\", \"J\", label=\"沉闷\")\n",
    "dot.edge(\"E\", \"K\", label=\"浊响\")\n",
    "dot.edge(\"D\", \"L\", label=\"浅白\")\n",
    "dot.edge(\"D\", \"M\", label=\"青绿\")\n",
    "\n",
    "dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22ed297b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier, plot_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48965d72",
   "metadata": {},
   "outputs": [],
   "source": [
    "idx_name = np.array(data.columns)[1:]\n",
    "idx_name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eeda05d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "train_data = std_data\n",
    "train_data = np.vstack([idx_name, train_data])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bab73b65",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(std_data.shape[1]):\n",
    "    _, std_data[:, i] = np.unique(std_data[:, i], return_inverse=True)\n",
    "std_data = std_data.astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3878572",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = std_data[:, :-1]\n",
    "Y = std_data[:, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "564fdc93",
   "metadata": {},
   "outputs": [],
   "source": [
    "Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20144a26",
   "metadata": {},
   "outputs": [],
   "source": [
    "model = DecisionTreeClassifier(random_state=42, max_depth=5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7a3a4fc",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "model.fit(X, Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9846e324",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_tree(model)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
